/*
 * Алгоритм Флойда-Варшалла
 * vim:foldmethod=marker:
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <unistd.h>
#include <assert.h>

#define N_MAX	100

/*****************************************************************************/

#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MAX(a, b)	((a) > (b) ? (a) : (b))

void
print_matrix(const int **a, const int n)
{
	register int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			(void) fprintf(stderr, "%6d%s", a[i][j], (j==n-1)?"\n":" ");
}

int
floyd_warshall(int **am, int **prev, const int n)
{
	register int i = 0, j = 0;
	int k = 0;
	int max = -1;

	for (; i < n; i++)
		for (j = 0; j < n; j++)
			prev[i][j] = (am[i][j] == -1) ? -1 : i;

#ifdef DEBUG
	print_matrix(am, n);
	putc('\n', stderr);
	print_matrix(prev, n);
#endif

	for (k = 0; k < n; k++) {
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++) {
				//fprintf(stderr, "· k=%d i=%d j=%d\n", k+1, i+1, j+1);
				if (am[i][k] != -1 && am[k][j] != -1
						&& (am[i][j] == -1 || am[i][j] > am[i][k] + am[k][j])) {
					//fprintf(stderr, "·   updating am[i][j]\n");
					am[i][j]   = am[i][k] + am[k][j];
					prev[i][j] = prev[k][j];
				}
			}
#ifdef DEBUG
		print_matrix(am, n);
		putc('\n', stderr);
		print_matrix(prev, n);
#endif
	}

	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			max = MAX(max, am[i][j]);

	return max;
}

int
main(void)
{
	int **am; //adjacency matrix
	int **prev;
	int n;
	int i = 0, j = 0;

	scanf("%d", &n);
	am   = (int **) calloc(n, sizeof *am);
	prev = (int **) calloc(n, sizeof *prev);
	for (i = 0; i < n; i++) {
		am[i]   = (int *) calloc(n, sizeof **am);
		prev[i] = (int *) calloc(n, sizeof **prev);
	}

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			scanf("%d", &am[i][j]);

	printf("%d\n", floyd_warshall(am, prev, n));

#ifdef DEBUG
	print_matrix(am,   n); putc('\n', stderr);
	print_matrix(prev, n);
#endif

	for (i=0;i<n;i++) {
		free(am[i]);
		free(prev[i]);
	}
	free(am); free(prev);
	return 0;
}
